#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

// 边节点类的实现
EdgeNode::EdgeNode() : dest(0), link(nullptr) {}

EdgeNode::EdgeNode(int dest, EdgeNode* link) : dest(dest), link(link) {}

EdgeNode::~EdgeNode() {}

// 获取目标节点
int EdgeNode::getDest() { return dest; }

// 获取下一个边节点
EdgeNode* EdgeNode::getNext() { return link; }

// 设置目标节点
void EdgeNode::setDest(int dest) { this->dest = dest; }

// 设置下一个边节点
void EdgeNode::setNext(EdgeNode* link) { this->link = link; }


// 顶点节点类的实现
VertexNode::VertexNode() : data(' '), firstEdge(nullptr) {}

VertexNode::VertexNode(char data, EdgeNode* firstEdge) : data(data), firstEdge(firstEdge) {}

// 析构函数，释放与顶点节点关联的边节点
VertexNode::~VertexNode() {
    EdgeNode* current = firstEdge;
    while (current) {
        EdgeNode* temp = current;
        current = current->getNext();
        delete temp; 
    }
}

// 获取顶点数据
char VertexNode::getData() { return data; }

// 获取第一个边节点
EdgeNode* VertexNode::getFirstEdge() { return firstEdge; }

// 设置顶点数据
void VertexNode::setData(char data) { this->data = data; }

// 设置第一个边节点
void VertexNode::setFirstEdge(EdgeNode* firstEdge) { this->firstEdge = firstEdge; }


// 图的实现
MyGraph::MyGraph() : nodeNum(0), edgeNum(0), VexList(nullptr) {}

// 构造函数，根据传入的节点和边的数量及列表初始化图
MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList) 
    : nodeNum(nodeNum), edgeNum(edgeNum) {
    VexList = new VertexNode[nodeNum]; 

    // 初始化每个顶点
    for (int i = 0; i < nodeNum; ++i) {
        VexList[i].setData(nodeList[i]);
        VexList[i].setFirstEdge(nullptr);
    }

    // 初始化每条边（无向图）
    for (int i = 0; i < edgeNum; ++i) {
        int start = edgeStartList[i];
        int end = edgeEndList[i];
        VexList[start].setFirstEdge(new EdgeNode(end, VexList[start].getFirstEdge())); 
        VexList[end].setFirstEdge(new EdgeNode(start, VexList[end].getFirstEdge())); 
    }
}

// 析构函数，释放顶点数组的内存
MyGraph::~MyGraph() { delete[] VexList; }

// 获取节点数量
int MyGraph::getNodeNum() { return nodeNum; }

// 获取边的数量
int MyGraph::getEdgeNum() { return edgeNum; }

// 打印图的信息，包括每个节点及其相邻节点
string MyGraph::printGraph() {
    stringstream ss;
    for (int i = 0; i < nodeNum; ++i) {
        ss << VexList[i].getData() << ":"; 
        EdgeNode* edge = VexList[i].getFirstEdge();
        while (edge != nullptr) {
            ss << " " << VexList[edge->getDest()].getData(); 
            edge = edge->getNext();
        }
        ss << "\n"; // 换行
    }
    string result = ss.str();
    result.erase(result.end()-1); 
    return result;
}

// 获取第一个邻居节点
int MyGraph::getFirstNeighbor(int v, int* visited) {
    (void)visited;
    EdgeNode* edge = VexList[v].getFirstEdge();
    return edge ? edge->getDest() : -1; 
}

// 获取下一个邻居节点
int MyGraph::getNextNeighbor(int v, int w, int* visited) {
    (void)visited;
    EdgeNode* edge = VexList[v].getFirstEdge();
    while (edge) {
        if (edge->getDest() == w) { 
            edge = edge->getNext();
            return edge ? edge->getDest() : -1;
        }
        edge = edge->getNext();
    }
    return -1; 
}

// 深度优先搜索实现
void MyGraph::DFS(int v, int* visited, string& result) {
    visited[v] = 1; 
    result += VexList[v].getData();
    result += ' ';
    
    // 获取邻居并递归访问
    for (int w = getFirstNeighbor(v, visited); w != -1; w = getNextNeighbor(v, w, visited)) {
        if (!visited[w]) {
            DFS(w, visited, result); 
        }
    }
}

// 图的深度优先遍历
string MyGraph::graph_DFS_Traverse() {
    string result;
    int* visited = new int[nodeNum] {}; 
    for (int i = 0; i < nodeNum; ++i) {
        if (!visited[i]) {
            DFS(i, visited, result); 
        }
    }
    delete[] visited; 
    return result; 
}

// 广度优先搜索实现
void MyGraph::BFS(int v, int* visited, string& result) {
    queue<int> q;
    visited[v] = 1;
    q.push(v);
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        result += VexList[current].getData();
        result += ' ';
        
        // 获取邻居并入队
        for (int w = getFirstNeighbor(current, visited); w != -1; w = getNextNeighbor(current, w, visited)) {
            if (!visited[w]) {
                visited[w] = 1;
                q.push(w);
            }
        }
    }
}

// 图的广度优先遍历
string MyGraph::graph_BFS_Traverse() {
    string result;
    int* visited = new int[nodeNum] {}; 
    for (int i = 0; i < nodeNum; ++i) {
        if (!visited[i]) {
            BFS(i, visited, result); 
        }
    }
    delete[] visited; 
    return result; 
}